/*

该二叉树的复制二叉树方法未实现，存在bug，所以在main函数调用时被注释掉了

*/
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;

struct BTreeNode {
    int data = 0;
    BTreeNode* left;
    BTreeNode* right;
};
class BTree {
public:
    BTree() {
    }
    //传参需要注意，二叉树是指针类型的，节点本身就是一个指针：*node。所以需要二级指针才能改变二叉树的内容
    void create(BTreeNode*& Node) {
        int data;
        cin >> data;
        if (data) {
            Node = new BTreeNode;//创建新节点
            Node->data = data;
            //cout<<"data:"<<data<<endl;
            create(Node->left);//创建这个节点的左右结点
            create(Node->right);
        }
        else {
            Node = NULL;
        }
    }
    //按层创建二叉树
    void levelCreate(BTreeNode*& Node) {
        queue <BTreeNode*> que;//引入队列
        int data;
        cin >> data;
        if (data) {
            Node = new BTreeNode;
            Node->data = data;
            que.push(Node);
        }
        else {
            Node = NULL;
            return;
        }
        while (!que.empty()) {
            BTreeNode* node = que.front();
            que.pop();
            //输入左边数据
            cin >> data;
            if (data) {
                node->left = new BTreeNode;
                node->left->data = data;
                que.push(node->left);
            }
            else {
                node->left = NULL;
            }
            //输入右边数据
            cin >> data;
            if (data) {
                node->right = new BTreeNode;
                node->right->data = data;
                que.push(node->right);
            }
            else {
                node->right = NULL;
            }
        }
    }
    //1 2 3 4 5 6 0 0 0 7 8 0 9 0 0 0 0 0 0
    void clear(BTreeNode*& Node) {
        BTreeNode* p = Node;
        if (p != NULL) {
            clear(Node->left);
            clear(Node->right);
            delete p;
        }
    }
    //前序遍历(根左右)
    void preorderTree(BTreeNode* Node) {
        if (Node != NULL) {
            cout << Node->data << " ,";
            preorderTree(Node->left);
            preorderTree(Node->right);
        }
    }
    //前序遍历非递归写法
    void NnredursionPreorder(BTreeNode* Node) {
        stack<BTreeNode*> node;
        node.push(Node);
        BTreeNode* pNode = Node;
        while (pNode != NULL || !node.empty()) {
            //1、先把节点打印，并且入栈，将节点的左孩子作为当前的节点
            //2、当节点不为空或者栈不为空，就取出栈顶，
            if (pNode != NULL) {

                cout << pNode->data << " ";
                node.push(pNode);
                pNode = pNode->left;
            }
            else {
                BTreeNode* treeNode = node.top();
                node.pop();
                pNode = pNode->right;

            }
        }
    }

    //中序遍历(左中右)
    void inorderTree(BTreeNode* Node) {
        if (Node != NULL) {
            inorderTree(Node->left);
            cout << Node->data << " ,";
            inorderTree(Node->right);
        }
    }

    //后序遍历（左右中）
    void postorderTree(BTreeNode* Node) {
        if (Node != NULL) {
            postorderTree(Node->left);
            postorderTree(Node->right);
            cout << Node->data << " ,";
        }
    }
    //层序遍历
    void levelTree(BTreeNode* Node) {
        queue<BTreeNode*> que;
        if (Node == NULL) return;
        else {
            que.push(Node);
            while (!que.empty()) {
                BTreeNode* node = que.front();
                cout << node->data << " ";
                que.pop();
                if (node->left != NULL) {
                    que.push(node->left);
                }
                if (node->right != NULL) {
                    que.push(node->right);
                }
            }
        }
    }
    //二叉树深度
    int depthOfTree(BTreeNode* Node) {
        if (Node) {
            return max(depthOfTree(Node->left), depthOfTree(Node->right)) + 1;
        }
        else {
            return 0;
        }
    }
    //返回节点总数目
    int getNodeNum(BTreeNode* Node) {
        if (Node) {
            return 1 + getNodeNum(Node->left) + getNodeNum(Node->right);
        }
        else {
            return 0;
        }
    }
    //返回叶子节点
    int getLeafNum(BTreeNode* Node) {
        if (!Node) {
            return 0;
        }
        else if (Node->left == NULL && Node->right == NULL) {
            return 1;
        }
        else {
            return getLeafNum(Node->left) + getLeafNum(Node->right);
        }
    }
    void swap(BTreeNode** Node) {
        BTreeNode* temp;
        if ((*Node)) {
            temp = (*Node)->left;
            (*Node)->left = (*Node)->right;
            (*Node)->right = temp;
            swap(&((*Node)->left));
            swap(&((*Node)->right));
        }
    }
    int copybtree(BTreeNode *T,BTreeNode **NewT)
    {

        if (T == NULL)
        {
            return NULL;
        }
        else
        {
            //创建新节点
            (*NewT) = new BTreeNode;
            //复制节点内容
            (*NewT)->data = T->data;
            //复制左子树
            copybtree(T->left,&(*NewT)->left);
            //复制右子树
            copybtree(T->right, &(*NewT)->right);
            //以上两行代码先创建左子树再创建右子树，如果顺序颠倒其创建的顺序就会颠倒，但是最终创建的二叉树还是一样的
        }
    }
};
int main() {
    cout << "请输入树的节点"<<"(以非数字结束）：";
    BTree tree;
    BTreeNode* root;
    BTreeNode* root1;
    //tree.create(root);
    tree.levelCreate(root);
    cout << "pre :";
    tree.preorderTree(root);
    cout << endl;
    cout << "in  :";
    tree.inorderTree(root);
    cout << endl;
    cout << "post:";
    tree.postorderTree(root);
    cout << endl;
    cout << "level:";
    tree.levelTree(root);
    cout << endl;
    cout << "NodeNum:" << tree.getNodeNum(root) << ",depth:" << tree.depthOfTree(root) << ",leaf:" << tree.getLeafNum(root) << endl;
 
    tree.swap(&root);
    cout << "pre :";
    tree.preorderTree(root);
    cout << endl;

   /* tree.copybtree(root, &root1);
    cout << "pre :";
    tree.preorderTree(root1);
    cout << endl;*/

    tree.clear(root);
    return 0;
}
